
/*
Description:

*/

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <unordered_map>
using namespace std;

class Solution {
public:
	int romanToInt(string s)
	{
		unordered_map<char, int> T = { { 'I' , 1 },
		{ 'V' , 5 },
		{ 'X' , 10 },
		{ 'L' , 50 },
		{ 'C' , 100 },
		{ 'D' , 500 },
		{ 'M' , 1000 } };

		int sum = T[s.back()];
		for (int i = s.length() - 2; i >= 0; --i)
		{
			if (T[s[i]] < T[s[i + 1]])
			{
				sum -= T[s[i]];
			}
			else
			{
				sum += T[s[i]];
			}
		}

		return sum;
	}

	int romanToInt0(string s) {
		typedef tuple<string, int> elem2;
		vector<elem2> roman2{
			{ "I",    1 },
			{ "II",   2 },
			{ "III",  3 },
			{ "IV",   4 },
			{ "V",    5 },
			{ "VI",   6 },
			{ "VII",  7 },
			{ "VIII", 8 },
			{ "IX",   9 },
			{ "X",    10 },
			{ "XX",   20 },
			{ "XXX",  30 },
			{ "XL",   40 },
			{ "L",    50 },
			{ "LX",   60 },
			{ "LXX",  70 },
			{ "LXXX", 80 },
			{ "XC",   90 },
			{ "C",	  100 },
			{ "CC",   200 },
			{ "CCC",  300 },
			{ "CD",   400 },
			{ "D",    500 },
			{ "DC",   600 },
			{ "DCC",  700 },
			{ "DCCC", 800 },
			{ "CM",   900 },
			{ "M",	  1000 },
			{ "MM",   2000 },
			{ "MMM",  3000 }
		};

		elem2 e;
		int num = 0;
		int cnt = 0;
		int pos = 0;
		for (int i = roman2.size(); i > 0; i--)
		{
			e = roman2[i - 1];
			cnt = get<0>(e).size();
			if (s.compare(pos, cnt, get<0>(e)) == 0)
			{
				pos += cnt;
				num += get<1>(e);				
			}
		}
		
		return num;
	}
};

int _romanToInt()
{
	string roman = "MCMXCIV"; //"III";// "IV";// "IX";// "LVIII";// 
	Solution solu;
	int num;// = 1994;// 58;// 9;// 4;// 3;

	num = solu.romanToInt(roman);

	cout << "roman: " << roman << endl;
	cout << "number: " << num << endl;
	
	return 0;
}